package hot_problems_100;

public class P11_0076 {
    /*
    * 求s中的最小子串，该子串应当包含字符串t中的全部字符（保证答案唯一）
    * 0 < s.length, t.length < 1e5
    * s和t 仅仅包含 大小写字母
    * */


    /*
    * 使用52长度的数组，模拟哈希表
    * 同样的我们使用一个match_count来避免一次性对比所有字符
    *
    * 使用一个滑动窗口[left, right) 来对应这个子串
    * 顺序遍历字符串s，持续添加字符到窗口中，如果match_count达到52，则开始尝试从left开始删除字符
    * */
    private int get_index(char c){
        if(c<='z' && c>='a'){
            return c - 'a';
        } else {
            return c - 'A' + 26;
        }
    }

    public String minWindow(String s, String t) {
        int[] char_nums = new int[52];
        for(int i=0; i<t.length(); i++){
            char_nums[get_index(t.charAt(i))] ++;
        }

        int[] substr_char_nums = new int[52];
        int match_count = 0;
        for(int i=0; i<52; i++){
            if(substr_char_nums[i] == char_nums[i]) match_count ++ ;
        }
        int left=0, right=0;
        String res = "";
        int res_len = 100001;
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            right ++;
            int index = get_index(c);
            substr_char_nums[index] ++;
            if(substr_char_nums[index] == char_nums[index]){
                match_count ++ ;
            }

            if(match_count == 52){
                int len = right - left;
                int start = left;
                for(int j=0; j<len; j++){
                    c = s.charAt(start+j);
                    index = get_index(c);
                    if(substr_char_nums[index]-1 >= char_nums[index]){
                        left ++;
                        substr_char_nums[index] --;
                    } else {
                        break;
                    }
                }
                if(right - left < res_len){
                    res = s.substring(left, right);
                    res_len = res.length();
                }

            }
        }
        return res;
    }
}
